Henry ’Blog
0%

<剑指offer> 剑指offer 03.04.05.06

发表于 更新于 分类于 Valine：

摘要：
03 数组中重复的数字
04 二维数组中的查找
05 替换空格
06 从尾到头打印链表

面试题03 数组中重复的数字

题目：

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//java
class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set=new HashSet<Integer>();
        int res=0;
        int n=nums.length;
        for(int i=0;i<n;i++){
            if(!set.add(nums[i])){
                res=nums[i];
                break;
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
#python3
class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        mySet=set()
        for num in nums:
            if num in mySet:
                return num
            else:
                mySet.add(num)

面试题04 二维数组中的查找

题目：

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//java
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix == null|| matrix.length == 0 || matrix[0].length == 0){
            return false;
        }
        int row=0;
        int col=matrix[0].length-1;
        while(row<matrix.length&&col>=0){
            if(target==matrix[row][col]){
                return true;
            }else if(target>matrix[row][col]){
                row++;
            }else{
                col--;
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
#python3
class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix: return False
        col,row =len(matrix[0])-1,0
        while col>=0 and row<len(matrix):
            if matrix[row][col]<target :row+=1
            elif matrix[row][col]>target : col-=1
            else: return True
        return False

面试题05 替换空格

题目：

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

解法：

1
2
3
4
5
6
7
8
//java
class Solution {
    public String replaceSpace(String s) {
            // String s1=s.toString();
            // String res=s1.replace(" ","%20");
            return s.toString().replace(" ","%20");
    }
}
1
2
3
4
#python3
class Solution:
    def replaceSpace(self, s: str) -> str:
        return s.replace(" ","%20")

面试题 06 从尾到头打印链表

题目：

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
//java
class Solution {
    public int[] reversePrint(ListNode head) {
		// 1.借助栈的方法
         LinkedList<Integer> stack=new LinkedList<Integer>();
     	 while(head!=null){
             stack.addLast(head.val);
            head=head.next;
        }
         int[] arr=new int[stack.size()];
        
         for(int i=0;i<arr.length;i++)
             arr[i]=stack.removeLast();
         return arr;
     }
}



class Solution {
    // 2.迭代法：
    ArrayList<Integer> tmp=new ArrayList<Integer>();
    public int[] reversePrint(ListNode head) {
        recur(head);
        int[] arr=new int[tmp.size()];
        for(int i=0;i<arr.length;i++){
            arr[i]=tmp.get(i);
        }
        return arr;
    }
    void recur(ListNode head){
        if(head==null)
            return;
        recur(head.next);
        tmp.add(head.val);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#python3
class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        # 递归法
        return self.reversePrint(head.next)+[head.val] if head else []
        # 借助栈
        stack = []
        while head:
            stack.append(head.val)
            head = head.next
        return stack[::-1]